A tree is a data structure including a set of parent/child relationships between nodes. For example, hierarchical data, e.g., computer network data, may be displayed in the form of a tree which describes the hierarchical relationship between nodes in a computer network. A tree may be used to display visual information in a browser or in a tree controlled graphical user interface.
A topology tree is an example of a tree used to display visual information. A topology tree may displays technical information regarding nodes in a distributed computer environment. In the topology tree, the number of nodes may be high, since thousands of indexes and queues may exist in a distributed computer environment of hundreds of services and hosts.
In certain cases, it may be desirable to compress a tree for various reasons. For example, the tree may be compressed in order to improve the visual display of the tree and the user traversal of the tree. A tree may be compressed by merging nodes into other nodes of the tree.
A conventional method for the compressing a tree involves adjusting referring tree nodes in a tree table. A tree table lists all the tree nodes in the tree. The conventional method scans all entries in a tree table below a tree node entry set for deletion. If a parent identifier is found that is the same as the identifier of the deleted node, its value is changed to the node identifier of the parent of the deleted node. If the tree control requires contiguous node identifier values, then all node identifier below the removed line in tree table are decreased by one place to fill the gap in the numbering of node identifier values. The conventional method is repeated for each removed line in the tree table. The higher the node identifier of the removed line in the tree table (i.e., the lower it is in the table), the smaller the number of remaining entries below the removed line in the tree table that have to be visited.
This conventional method for the compressing a tree node provides that many table lines are visited (reading, comparing, or changing). If the table has N lines and M nodes are removed, then in the worst case (where all nodes to be removed are near the top of the table) the number of visited nodes is on the order of M×N. If the nodes to be removed are distributed evenly in the table, then the number of table lines to be visited is on the order of ½×M×N.
However, performing compression on lengthy trees may involve a considerable amount of processing load. The number of nodes may be high in a distributed computer environment and a tree may consist of N=2000 nodes from which M=100 nodes may be removed as a result of node merging. In such a case, the number of visited nodes whose identifiers have to be investigated and perhaps changed is on average ½×M×N˜100 000. The precise number depends on the distribution of nodes to be removed over the table. Visiting such a large number of nodes represents a considerable processing load for displaying the reduced tree.